package LearnAlgorithm.c_递归and查找排序;

public class m求a的n次幂 {
	public static void main(String[] args) {
		long b1 = System.currentTimeMillis();
		System.out.println(fun1(2, 30));
		/*
		 * for (int i = 0; i < 1000000; i++) { fun3(15); }
		 */
		long b2 = System.currentTimeMillis();
		System.out.println((b2 - b1) + "ms");//0ms是因为算的太快了
		
		long c1 = System.currentTimeMillis();
		System.out.println(fun2(2, 30));
		long c2 = System.currentTimeMillis();
		System.out.println((c2 - c1) + "ms");
	}
	
	/**
	 * O(n)
	 * @param a
	 */
	public static int fun1(int a, int n) {
		int res = 1;
		for (int i = 0; i < n; i++) {
			res *= a;
		}
		return res;
	}
	
	/**
	 * O(logn)
	 * @param a
	 * @param n
	 * @return
	 */
	public static int fun2(int a, int n) {
		if (n == 0) {
			return 1;//这里设置递归出口
		}
		
		int res = a;
		int ex = 1;
		while ((ex<<1) <= n) {
			res *= res;
			ex <<= 1;//幂指数翻倍
		}
		//肯定存在8翻倍成16，16>15的情况
		//那么剩下的n-ex次方，还没有乘进去
		//那么就只能使用递归！！！这里的思想很巧妙！！
		return res*fun2(a, n-ex);
	}
	
	private static long fun3(long n) {
		if (n == 1 || n == 2) {
			return 1;
		}
		return fun3(n-1) + fun3(n-2);
	}
}
